/*
 * @lc app=leetcode.cn id=1895 lang=golang
 *
 * [1895] 最大的幻方
 */
package Solutions

// @lc code=start
func largestMagicSquare(grid [][]int) int {
	var preSum = make([][][4]int, len(grid)+1)
	for i := 0; i < len(preSum); i++ {
		preSum[i] = make([][4]int, len(grid[0])+1)
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			i1 := i + 1
			j1 := j + 1
			preSum[i1][j1][1] = preSum[i1-1][j1][1] + grid[i][j]
			preSum[i1][j1][0] = preSum[i1][j1-1][0] + grid[i][j]
			preSum[i1][j1][2] = preSum[i1-1][j1-1][2] + grid[i][j]

		}
	}
	for i := 0; i < len(grid); i++ {
		for j := len(grid[i]) - 1; j >= 0; j-- {
			if i-1 >= 0 && j+1 < len(grid[i]) {
				preSum[i][j][3] = preSum[i-1][j+1][3] + grid[i][j]
			} else {
				preSum[i][j][3] = grid[i][j]
			}

		}
	}

	var ans = 1
	for i := 0; i < len(grid); i++ {

		for j := 0; j < len(grid[i]); j++ {
			var k = 1
		loopK:
			for ; i-k >= 0 && j-k >= 0; k++ {

				i1 := i + 1
				j1 := j + 1
				sum := preSum[i1][j1][0] - preSum[i1][j-k][0]
				for m := 1; m <= k; m++ {
					if sum != preSum[i1-m][j1][0]-preSum[i1-m][j-k][0] {
						continue loopK
					}
				}
				for m := 0; m <= k; m++ {
					if sum != preSum[i1][j1-m][1]-preSum[i-k][j1-m][1] {
						continue loopK
					}
				}
				if sum != preSum[i1][j1][2]-preSum[i-k][j-k][2] {
					continue
				}
				if sum != preSum[i][j-k][3]-preSum[i-k][j][3]+grid[i-k][j] {
					continue
				}
				if ans < k+1 {
					ans = k + 1
				}

			}
		}
	}
	return ans

}

// @lc code=end
// [100038,100045,100021,100014,100072,100021,100064,100046,100069,100071,100069,100063,100057,100095,100019,100007],
// [100068,100075,100076,100017,100086,100064,100092,100085,100044,100007,100075,100044,100032,1,100077,100083],
// [100092,100095,100097,100047,100067,100089,100026,100088,100095,100071,100031,100068,100064,100055,100013,100071],
// [100084,100033,100009,100050,100027,100064,100088,100061,100017,100051,100082,100073,100077,100054,100048,100001],
// [100004,100007,100049,100089,100049,100038,100006,100046,100023,100073,100082,100012,100074,100038,100010,100097],
// [100035,100073,100025,100099,100030,100090,100032,100074,100096,100092,100041,100091,100025,100054,100017,100100],
// [100048,100036,100031,100089,100050,100031,100091,100091,100069,100075,100032,100077,100066,100052,100089,100050],
// [100064,100058,100040,100019,100016,100090,100099,100091,100069,100071,100003,100031,100043,100022,100016,100082],
// [100036,100070,100059,100041,100008,100071,100076,100068,100033,100065,100057,100004,100097,100092,100043,100051],
// [100098,100026,100005,100049,100051,100087,100051,100068,100054,100002,100075,100080,100100,100023,100030,100013],
// [100064,100066,100028,100077,100071,100003,100003,100019,100011,100003,100039,100053,100099,100022,100061,100083]]
